package hash.medium;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 字母异位词分组
 * 示例 1:
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 *
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 *
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/group-anagrams
 */
public class GroupAnagrams_49 {

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length <= 1) {
            List<List<String>> li = new ArrayList<>();
            ArrayList<String> objects = new ArrayList<>();
            if (strs.length == 1)
                objects.add(strs[0]);
            li.add(objects);
            return li;
        }
        int[] arr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

        Map<Double, List<String>> map = new HashMap<>();
        for (String str : strs) {
            double sum = 1.0;
            for (char c : str.toCharArray()) {
                sum *= arr[c - 'a'];
            }
            if (map.containsKey(sum)) {
                List<String> strings = map.get(sum);
                strings.add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(sum, list);
            }
        }
        List<List<String>> li = new ArrayList<>();
        for (double lo : map.keySet()) {
            li.add(map.get(lo));
        }
        return li;
    }

    public static void main(String[] args) {
        GroupAnagrams_49 ga = new GroupAnagrams_49();
        String[] s = {"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"};
        ga.groupAnagrams(s);
    }

}
